// 2025/11/11
// 随即链表的复制

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> mp;
        mp[nullptr] = nullptr;
        Node* cur = head;
        while(cur)
        {
            mp[cur] = new Node(cur->val);
            cur = cur->next;
        }
        for(auto &[src, dest] : mp)
        {
            if(src == nullptr)
                continue;
            dest->next = mp[src->next];
            dest->random = mp[src->random];
        }
        return mp[head];
    }
};